package com.self.structure;

import java.util.Arrays;
import java.util.Random;

public class SortMain {

    public static void main(String[] args) {

        int[] src = new int[20];
        countSortTest(src,20);

        String a = "abcklskjgkljeisaaadkljadlfkjalsdfiefkljadfKJHHLFHSINAJKDKIEJDKLSJ";

        Arrays.sort(a.toCharArray(),0,a.length());
        StringCountSort stringCountSort = new StringCountSort();
        System.out.println(stringCountSort.sort(a));

    }

    private static void countSortTest(int[] src,int max) {

        Random random = new Random();

        // 初始化
        for (int i = 0; i < src.length;i++) {
            src[i] = random.nextInt(max);
        }

        // 输出原始数据
        for (int v : src) {
            System.out.print(v+",");
        }
        System.out.println();

        Sort sort = new CountSort(max);
        int[] rs = sort.sort(src);

        if(rs != null) {
            for (int v : rs) {
                System.out.print(v+",");
            }
        }

        System.out.println();
    }
}

/**
 * 计数排序
 */
class CountSort implements Sort {

    private int wide;

    CountSort(int wide) {
        this.wide = wide;
    }

    @Override
    public int[] sort(int[] arr) {

        if(arr == null || arr.length == 0) {
            return arr;
        }

        int[] countArr = new int[wide+1];

        // 频率统计
        for (int v : arr) {
            countArr[v + 1] += 1;
        }

        // 确定索引位置
        int len = countArr.length - 1;
        for (int i = 0; i < len; i++) {
            countArr[i+1] += countArr[i];
        }

        // 输出
        int[] rs = new int[arr.length];
        for (int v : arr) {
            rs[countArr[v]++] = v;
        }

        return rs;
    }
}

class StringCountSort {

    String sort(String src) {

        if(src == null || src.trim().length() == 0) {
            return src;
        }

        int[] countArr = new int[124];
        int srcLen = src.length();
        for (int i = 0; i < srcLen; i++) {
            countArr[src.charAt(i)+1] += 1;
        }

        // 确定索引位置
        int len = countArr.length - 1;
        for (int i = 0; i < len; i++) {
            countArr[i+1] += countArr[i];
        }

        // 输出
        char[] rs = new char[src.length()];
        for (int i = 0; i < srcLen; i++) {
            rs[countArr[(int)src.charAt(i)]++] = src.charAt(i);
        }

        return new String(rs);
    }
}
